package com.ztom.top100;

import java.util.ArrayList;
import java.util.List;

/**
 * 删除无效的括号
 * <p>
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 *
 * @author ZhangTao
 */
public class Code77RemoveInvalidParentheses {

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        // 记录左右括号需要删除的个数
        int l = 0;
        int r = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                l++;
            } else if (s.charAt(i) == ')') {
                if (l == 0) {
                    r++;
                } else {
                    // 如果左右括号匹配
                    l--;
                }
            }
        }
        process(s, 0, l, r, res);
        return res;
    }

    private void process(String str, int start, int l, int r, List<String> res) {
        if (l == 0 && r == 0) {
            // 无效括号都已经删除, 检查当前字符串是否有效
            if (isValid(str)) {
                res.add(new String(str));
            }
            return;
        }
        for (int i = start; i < str.length(); i++) {
            if (i > start && str.charAt(i) == str.charAt(i - 1)) {
                // (((()) 去除重复校验
                continue;
            }
            if (str.length() - i < l + r) {
                // 都没有办法再删除字符了
                return;
            }
            // 删除掉 i 位置的字符
            String s = str.substring(0, i) + str.substring(i + 1);
            if (l > 0 && str.charAt(i) == '(') {
                process(s, i, l - 1, r, res);
            }
            if (r > 0 && str.charAt(i) == ')') {
                process(s, i, l, r - 1, res);
            }
        }
    }

    private boolean isValid(String str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                count++;
            } else if (str.charAt(i) == ')') {
                count--;
                // 如果右括号先出现, 不合法
                if (count < 0) {
                    return false;
                }
            }
        }
        return count == 0;
    }
}
